Masala #1033

Xotira 64 MB Vaqt 1250 ms Qiyinchiligi 45 %
14

  

Kill the monsters!

“Kill the monsters!” nomli o‘yin mavjud. Bu o‘yinda, siz tushunib ulgurganingizdek, monsterlar bor va ularni o‘ldirish lozim.

O‘yin maydoni bitta uzun kesma bo‘lib, u \(-10^9\) dan \(10^9\) gacha raqamlangan koordinatalardan iborat. Koordinata 3 xil holatda bo‘lishi mumkin: koordinata bo‘sh, koordinatada 1 ta monster bor yoki koordinatada 1 ta devor bor. Maydondagi jami devorlar va monsterlar soni \(n\) ga teng. Har bir monster o‘zining sog‘lik darajasiga ega.

Siz \(k\) marta quyidagi ishni qila olasiz:

  • o‘yin maydonida devor bo‘lmagan va oldin belgilanmagan koordinatani tanlash va uni belgilash

So‘ng barcha belgilangan koordinatalarda bir vaqtda olov yoqasiz.

Qaysidir koordinatada olov yongan bo‘lsa, 1 soniyada shu koordinatadagi monsterning sog‘lik darajasi 1 birlikka kamayadi, hamda olov oldin yonmagan va devori yo‘q bo‘lgan qo‘shni koordinataga ham o‘tadi. Olov yongan koordinatada u hech qachon o‘chmaydi. Monsterning sog‘lik darajasi 0 ga tushsa, u o‘ldi deb hisoblanadi.

Yondirish uchun \(k\) ta koordinatani optimal tanlab ularni yondirgach, eng kami bilan necha soniyadan so‘ng barcha monsterlar o‘lishini toping.

Optimal tanlovda ham, \(10^{100}\) soniyadan so‘ng tirik monster topilsa, “IMPOSSIBLE” so‘zini qo‘shtirnoqlarsiz chiqaring.


Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida ikkita butun sonlar - \(n,k(1 \le k \le n \le 2*10^5)\) kiritiladi.

Keyingi \(n\) ta qatorning har birida maydondagi bo‘shmas kataklar ko‘rsatiladi.

Monster uchun yangi qatorda ‘M’ belgisi va yana 2 ta butun son - \(x(-10^9 \le x \le 10^9)\) monster turgan koordinata va \(h(1 \le h \le 10^9)\) monsterning sog‘lik darajasi kiritiladi.

Devor uchun yangi qatorda ‘W’ belgisi va yana 1 ta butun son - \(x(-10^9 \le x \le 10^9)\) devor turgan koordinata kiritiladi.

Barcha testlar tepadagi shartlarni qanoatlantirishi kafolatlanadi.


Chiquvchi ma'lumotlar:

Yagona qatorda masala javobini chiqaring.


Misollar
# input.txt output.txt
1
3 2
M 1 4
W 2
M 3 6
6
2
3 1
M 1 4
W 2
M 3 6
IMPOSSIBLE
3
2 1
M -1000000000 1
M 1000000000 2
1000000002
Izoh:

Birinchi testda:

  • 1 koordinatada sog‘ligi 4 bo‘lgan monster bor.
  • 2 koordinatada devor bor.
  • 3 koordinatada sog‘ligi 6 bo‘lgan monster bor.

Yondirish uchun 2 ta koordinatani belgilash lozim. 1 va 3 koordinatani belgilab ularni yondirsak, 6 soniyada barcha monsterlar o‘ladi. Bu eng yaxshi natija ekanligini isbotlasa bo‘ladi.

 

Ikkinchi testda:

Devor va monsterlar xuddi birinchi testdagidek, yagona farqi yondirish uchun faqatgina       1 ta koordinatani tanlash mumkin. Bu holatda javob “IMPOSSIBLE”. Chunki qaysi koordinatani yondirmaylik, bitta monster o‘ladi, boshqa monster esa devor sababli \(10^{100}\) soniyadan so‘ng ham tirik qoladi.

 

Uchinchi testda:

Faqatgina 1 ta koordinatani yondirish mumkin. 0 koordinatani tanlash optimal bo‘ladi. Bunda 1-monsterga yetib olib uni o‘ldirish uchun \(10^9+1\) soniya vaqt kerak. 2-monsterga yetib olib uni o‘ldirish uchun esa \(10^9+2\) soniya vaqt kerak. Jami \(10^9+2\) soniyadan so‘ng barcha monsterlar o‘lgan bo‘ladi.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin